package utils;

import java.io.*;
import java.util.HashMap;
import java.util.Map;

/**
 * 结构为
 *                  (head)
 *       c1           c2           c3
 *   c11    c12   c21     c22   c31    c32
 *   ....
 * 字典树工具类
 * @author bug-fsh
 */
public class TrieTreeUtils {

    //缓存key
    private String cacheKey;

    //字典树头结点
    private TrieTreeNode head;

    //文件名称
    private String fileName;

    public TrieTreeUtils(String cacheKey, String fileName) {
        this.cacheKey = cacheKey;
        this.fileName = fileName;
        this.init();
    }

    /**
     * 初始化字典树
     */
    private void init() {
        if (head == null) {
            head = new TrieTreeNode();
            FileInputStream fileInputStream = null;
            InputStreamReader inputStreamReader = null;
            BufferedReader bufferedReader = null;
            try {
                fileInputStream = new FileInputStream(fileName);
                inputStreamReader = new InputStreamReader(fileInputStream, "utf-8");
                bufferedReader = new BufferedReader(inputStreamReader);
                String words = null;
                while ((words = bufferedReader.readLine()) != null) {
                    if (StringUtils.isEmpty(words)) {
                        continue;
                    }
                    words.trim();
                    head.addWords(words);
                }
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        if (head.empty()) {
            //存放在缓存中
        }
    }

    /**
     * 从字典树中查找词条
     * @param words
     * @return
     */
    public boolean searchWords(String words) {
        if (head.empty()) return false;
        return head.searchWords(words);
    }


    /**
     * 字典树节点结构
     */
    private class TrieTreeNode {

        //存放节点数据
        private String value;

        //子节点
        private Map<Integer, TrieTreeNode> children = new HashMap<Integer, TrieTreeNode>();

        //从头节点到此节点是否为一条完整索引
        private boolean fullIndex = false;

        public TrieTreeNode() {

        }

        public TrieTreeNode(String value) {
            this.value = value;
        }

        public TrieTreeNode(String value, boolean fullIndex) {
            this(value);
            this.fullIndex = fullIndex;
        }

        public TrieTreeNode(String value, boolean fullIndex, Map<Integer, TrieTreeNode> children) {
            this(value, fullIndex);
            this.children = children;
        }

        /**
         * 为该节点增加词条
         * @param words
         */
        public void addWords(String words) {
            TrieTreeNode temp = this;
            TrieTreeNode node = null;
            StringBuffer stringBuffer = new StringBuffer(words);
            for (int i = 0; i < stringBuffer.length(); i++) {
                node = new TrieTreeNode(stringBuffer.substring(i, i+1));
                if (i == stringBuffer.length() - 1) {
                    node.fullIndex = true;
                }
                if (!temp.children.containsKey(node.hash())) {
                    temp.children.put(node.hash(), node);
                }
                temp = node;
            }
        }

        /**
         * 查找词条
         * @param words
         * @return
         */
        public boolean searchWords(String words) {
            if (StringUtils.isEmpty(words)) return false;
            TrieTreeNode temp = this;
            TrieTreeNode node = null;
            StringBuffer stringBuffer = new StringBuffer(words);
            for (int i = 0; i < stringBuffer.length(); i++) {
                node = new TrieTreeNode(stringBuffer.substring(i, i+1));
                if (!temp.children.containsKey(node.hash())) {
                    return false;
                }
                temp = temp.children.get(node.hash());
                if (i == stringBuffer.length() - 1 && temp.fullIndex) {
                    return true;
                }
            }
            return false;
        }

        /**
         * 节点为空
         * @return
         */
        private boolean empty() {
            if(children == null || children.size() == 0) return true;
            return false;
        }

        /**
         * 生成hash值，为子节点map的key值
         * @return
         */
        private int hash() {
            return value.hashCode();
        }
    }

    public static void main(String [] args) {
        //自己定义文件
        String filaName = "D:\\java\\java-utils\\src\\words.txt";
        TrieTreeUtils tireTreeUtils = new TrieTreeUtils("filter_words_key", filaName);
        if (!tireTreeUtils.searchWords("好朋")) {
            System.out.println("不存在");
        }
    }
}


